// 1765. 地图中的最高点


/**
 * 1.数组先减去1，水域自然全部变成0未处理的格子变成-1 同时用一个数组存储当前海平面
 * 2.将当前海平面周围的格子全部赋值为0+1,同时将这些刚处理的格子作为新的海平面数组，然后
 * 海平面+1，继续下一轮
 * 3.水到顶，待处理的格子都被淹没了，结束
 * 
*/
/**
 * @param {number[][]} isWater
 * @return {number[][]}
 */
var highestPeak = function (isWater) {
    debugger
    var needCast = [];
    for (var i = 0; i < isWater.length; i++) {
        for (var j = 0; j < isWater[i].length; j++) {
            // 先处理水域
            isWater[i][j]--;
            if (isWater[i][j] == 0) {
                needCast.push([i, j]);
            }
        }
    }
    var waterHeight = 0;

    while (true) {
        var newNeedCast = [];
        for (var p of needCast) {
            higherNearWater(isWater, p[0], p[1], waterHeight + 1, newNeedCast);
        }
        needCast = newNeedCast;
        if (needCast.length == 0) {
            break;
        }
        waterHeight++;
    }
    return isWater;
};
var higherNearWater = function (map, x, y, height, newNeedCast) {
    if (map[x][y + 1] == -1) {
        map[x][y + 1] = height;
        newNeedCast.push([x, y + 1]);
    }
    if (map[x][y - 1] == -1) {
        map[x][y - 1] = height;
        newNeedCast.push([x, y - 1]);
    }
    if (map[x - 1] && map[x - 1][y] == -1) {
        map[x - 1][y] = height;
        newNeedCast.push([x - 1, y]);
    }
    if (map[x + 1] && map[x + 1][y] == -1) {
        map[x + 1][y] = height;
        newNeedCast.push([x + 1, y]);
    }
}


// dp
var highestPeak = function (isWater) {
    let m = isWater.length, n = isWater[0].length
    const dp = Array.from(Array(m), () => Array(n).fill(0))
    const max = m * n
    // 先去使用左上到右下的dp
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (isWater[i][j] === 1) continue
            // 如果值为0的话,则先去计算它到左上的最小值
            let min = max
            // 计算上位置的最小值
            if (i > 0) {
                min = Math.min(min, dp[i - 1][j] + 1)
            }
            // 计算左侧位置的最小值
            if (j > 0) {
                min = Math.min(min, dp[i][j - 1] + 1)
            }
            dp[i][j] = min
        }
    }
    // 从右下到左上的DP
    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (i < m - 1) {
                dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1)
            }
            if (j < n - 1) {
                dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1)
            }
        }
    }

    return dp
}
highestPeak([[0, 1], [0, 0]])